Search for: All records

On hypergraphs withmhyperedges andnvertices, wherepdenotes the total size of the hyperedges, we provide the following results:We give an algorithm that runs in\(\widetilde{O}(mn^{2k-2})\)time for finding a minimumk-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimumk-cut problem, fork> 2.We give an algorithm that runs in\(\widetilde{O}(n^{\max \lbrace r,2k-2\rbrace })\)time for finding a minimumk-cut in hypergraphs of constant rankr. This algorithm betters the previous best running times for both the minimum cut and minimumk-cut problems for dense hypergraphs.Both of our algorithms are Monte Carlo, i.e., they return a minimumk-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a genericbranching randomized contractiontechnique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs. 

We provide the first sub-linear space and sub-linear regret algorithm for online learning with expert advice (against an oblivious adversary), addressing an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC 2022). We also demonstrate a separation between oblivious and (strong) adaptive adversaries by proving a linear memory lower bound of any sub-linear regret algorithm against an adaptive adversary. Our algorithm is based on a novel pool selection procedure that bypasses the traditional wisdom of leader selection for online learning, and a generic reduction that transforms any weakly sub-linear regret o(T) algorithm to T1-α regret algorithm, which may be of independent interest. Our lower bound utilizes the connection of no-regret learning and equilibrium computation in zero-sum games, leading to a proof of a strong lower bound against an adaptive adversary. 

We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust linear algebraic algorithms when the updates to the input are sparse but given by an adversary with access to a query oracle. We also study robust algorithms in the standard centralized setting, where an adversary queries an algorithm in an adaptive manner, but the number of interactions between the adversary and the algorithm is bounded. We first recall a unified framework of [HKM+20, BKM+22, ACSS23] which is roughly a quadratic improvement over the na ̈ıve implementation, and only incurs a logarithmic overhead in query time. Although the general framework has diverse applications in machine learning and data science, such as adaptive distance estimation, kernel density estimation, linear regression, range queries, and point queries and serves as a preliminary benchmark, we demonstrate even better algorithmic improvements for (1) reducing the pre-processing time for adaptive distance estimation and (2) permitting an unlimited number of adaptive queries for kernel density estimation. Finally, we complement our theoretical results with additional empirical evaluations.